/**
 * 347. 前 K 个高频元素
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 */

const { displayBaseArray } = require('../../libs/public');

/**
 * @param {any[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {([number, number])[]} heap
 * @param {number} length
 */
function resolveHeap(heap, length) {
  let val = 0;
  let left = 0;
  let leftVal = 0;
  let right = 0;
  let rightVal = 0;
  for (let i = Math.floor(length / 2) - 1; i >= 0; i -= 1) {
    left = i * 2 + 1;
    [, leftVal] = heap[left];
    right = left + 1;
    rightVal = right >= length ? -Infinity : heap[right][1];
    [, val] = heap[i];
    if (val >= leftVal && val >= rightVal) {
      continue;
    }
    if (leftVal >= rightVal) {
      swap(heap, i, left);
    } else {
      swap(heap, i, right);
    }
  }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {
  let { length } = nums;
  if (length <= 1) {
    return nums;
  }
  const map = new Map();
  for (let i = 0; i < length; i += 1) {
    let record = map.get(nums[i]);
    if (!record) {
      record = [nums[i], 0];
      map.set(nums[i], record);
    }
    record[1] += 1;
  }
  const records = Array.from(map.values());
  length = records.length;
  const stack = new Array(k).fill(0);
  let top = -1;
  let head = 0;
  while (top < k - 1) {
    resolveHeap(records, length);
    [[head]] = records;
    top += 1;
    stack[top] = head;
    length -= 1;
    swap(records, 0, length);
  }
  return stack;
}

console.log(displayBaseArray(topKFrequent([3, 1, 2, 1, 1, 2], 2)) === '[1,2]');
console.log(displayBaseArray(topKFrequent([1], 1)) === '[1]');
console.log(displayBaseArray(topKFrequent([5, 3, 1, 1, 1, 3, 73, 1], 2)) === '[1,3]');
